With the advancement of computer technologies and understanding of basic physical phenomena or systems (e.g., engine operation, fluid flow, heat transfer, structural stress and strain analysis, etc.), three-dimensional (3D) computer simulation has become more of an important feature in physical system development, analysis, and evaluation. The computer simulation (modeling) often involves the building of a finite element mesh (collection of discrete set of points defined as nodes) to model the physical system. The accuracy of finite element mesh generation is related to the geometric complexity (including representing the physical system by a set of mathematical equations) of the physical system including the number of finite elements in the mesh, the order of those elements, and the quality of those finite elements.
A number of mesh-generating algorithms (e.g., parametric mapping, Dicer algorithm, Paving algorithm, Whisker-Weaving algorithm, etc.) have been developed to attempt to generate high-quality meshes with greater accuracy and reduced user interaction for generating the mesh. However, each algorithm has its own set of strengths and weaknesses, and therefore may only be suitable for a particular geometry while being ineffective for another. Therefore, there is still a need to generate high-quality meshes for all types of geometry, including quadrilateral surface meshes that are robust, accurate, and reduce user interaction time.
As described herein, the generation of a dual (for a surface) within a dual space may be an effective tool for producing a high-quality mesh for quadrilateral surfaces. It is noted that terms used within the specification, in accordance with embodiments of the present invention, will be defined within the specification and further definition may be found within the Glossary of Terms in Appendix A. FIGS. 1A-1G illustrate the process for generating a dual of a surface as found in the prior art. FIG. 1a shows a portion 100 of a surface (mesh) in primal space. It is noted that portion 100 may also be the complete mesh. A dual of the surface is generated by connecting opposite edges of a quadrilateral element using a chord 102 (see Appendix A for glossary of terms) as shown. As shown in FIG. 1A, chord 102 (a dual chord) connects the opposite edges for a vertical row of quadrilateral elements 104, 106, 108, 110, 112, 114, and chord 102 may be composed of individual, connect chord segments such as chord segment 105 connecting opposite edges of quadrilateral element 104. Also, as shown in FIG. 1a, individual chords used in generating the dual of the surface may each be given a unique identification number (e.g., chord 102 labeled as “1”). In the dual space generated, chord 102 is equivalent (the dual) to the row of quadrilateral elements 104, 106, 108, 110, 112, 114 in the primal space.
The generation of the dual continues as shown in FIGS. 1B-1G as the opposite edges of more rows of quadrilateral elements are connected using further chords (e.g., 118, 120, 122, 124, 126, 128, 130, 132) until a dual for the entire portion of the surface 100 (composed of the intersecting chords) has been completed. The dual is generated with adherence to the following rules: 1) chords may not be tangent, 2) two chords may only intersect in the interior of a quadrilateral element, and 3) only two chords may intersect at any given point.
As shown in FIG. 2 from the prior art, other elements are created from the generation of the dual of surface portion 100. A two-dimensional (2D) cell region 202 may be generated, as shown in FIG. 2, that is defined as an n-sided polygon with the sides composed of individual chord segments from chords 102, 120, 122, 124 (see glossary in Appendix A). Also, every cell region includes a single node (e.g., node 204) from the original surface portion 100. Cell region 202 is equivalent (the dual) to node 204 within the dual space generated. Also, a centroid 206 may be generated that is defined as the intersection of two chords 102, 118 in the dual space where every intersection of chords (e.g., 102, 118) in the dual space includes one quadrilateral element (e.g., 106) in the original surface 100 (see glossary in Appendix A). Centroid 206 is equivalent (the dual) to quadrilateral element 106 within the dual space generated. Also, Table A in Appendix B shows the relationship between the original surface elements and dual entities in two dimensions.
Therefore, due to the disadvantages of current meshing algorithms, there is a need to provide a computer modeling technique that uses duals to generate and modify quadrilateral surface meshes while maintaining accuracy, reduced user interaction time, and high quality of the resulting meshes.